import javax.swing.tree.TreeNode;
import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Admin
 * Date: 2022-06-04
 * Time: 19:58
 */
public class TestDemo {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {

        if(root1 == null) {
            return root2;
        }

        if(root2 == null) {
            return root1;
        }

        TreeNode root = new TreeNode(root1.val+root2.val);
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }

    public int widthOfBinaryTree(TreeNode root) {
        if(root == null) return 0;

        Deque<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int max =0;

        while(!que.isEmpty()) {
            int size = que.size();
            max = Math.max(max,que.getLast().val - que.getFirst().val+1);
            while(size > 0) {
                TreeNode node = que.poll();
                size--;
                if(node.left != null) {
                    node.left.val = node.val * 2;
                    que.offer(node.left);
                }

                if(node.right !=null) {
                    node.right.val = node.val *2+1;
                    que.offer(node.right);
                }
            }
        }
        return max;
    }

    public int carFleet(int target, int[] position, int[] speed) {
        if(position.length == 1) return 1;
        int n = position.length;

        double[][] tmp = new double[n][2];
        for(int i = 0;i < n;i++) {
            tmp[i][0] = position[i];
            tmp[i][1] = (double)(target-position[i])/speed[i];
        }

        Arrays.sort(tmp, Comparator.comparingDouble(a->a[0]) );

        double max = tmp[n-1][1];
        int count = 0;
        for(int i = n-1;i >=1; i--) {
            if(max < tmp[i-1][1]) {
                count++;
                max = tmp[i-1][1];
            }
        }
        count++;

        return count;
    }

}
